//18. 四数之和
// 思路：先排序，用目标值减去这个数字，此时就是三数之和的思路了，双指针仍是题眼


#include <vector>
using namespace std;

class Solution
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target)
    {
        vector<vector<int>> ret;

        // 1. 先排序
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n; )
        {
            // 2. 利用 三数之和
            for(int j = i+1; j < n; )
            {
                // 双指针算法
                long _target = (long)target - nums[i] - nums[j];// 整型存不下，用long存储，需要强转
                int left = j+1, right = n-1;
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum < _target) left++;
                    else if(sum > _target) right--;
                    else
                    {
                        ret.push_back({nums[i], nums[j], nums[left++], nums[right--]});
                        // 去重left，right
                        while(left < right && nums[left] == nums[left-1]) left++;
                        while(left < right && nums[right] == nums[right+1]) right--;
                    }           
                }
                // 去重j
                j++;
                while(j < n && nums[j] == nums[j-1]) j++;
            }
            // 去重i
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }      
    }
};